27/02/2021

Problema

  • Descrição:
    • Função:
      • Minimizar o número de pontos de acesso (Pa’s) na área de 800 x 800 metros que atendam à demanda de 475 clientes (Pd’s).
    • Restrições:
      • O alcance de cada Pa é um círculo com raio de 85 metros.
      • O número de Pa’s não deve ultrapassar 100.
      • A soma da demanda dos Pd’s cobertos por um dado Pa não deve ultrapassar 150 Mbps.

Espaço de busca

  • Escala:
    • Continua:
      • Existem infinitas coordenadas de possíveis localizações para os Pa’s tornando o problema computacionalmente insolúvel.
    • Discreta:
      • Considerando a área de 800 x 800 metros discretizada em inteiros, existem 640.000 possíveis localizações para os Pa’s tornando o problema computacionalmente intratável.
      • Matrizes \(M_{(i,j)}\) foram construídas para discretizar o espaço de busca com \(i, j \in \{1, 2, ..., 800 \}\).

Desenho do Algoritmo

  • Testes dos Espaços:
    • Espaços discretos menores que \(M_{(8,8)}\) não apresentaram solução ótima.
    • Espaços maiores que \(M_{(150,150)}\) apresentaram custo computacional muito elevado.
  • Implementação:
    • O algorítimo foi desenhado para escanear os espaços discretos de \(M_{(8,8)}\) até \(M_{(150,150)}\) na área de 800 x 800 com intervalos iguais entre os pontos.
    • Para ilustrar, foi considerado o espaço de \(M_{(9,9)}\), que representa 81 possíveis localizações para os Pa’s.

Gráfico do Espaço de Busca

Iterações do Algoritmo

  • Laço:
    • A cada iteração o algoritmo inspeciona cada coordenada do espaço discretizado de possíveis localizações dos Pa’s e determina o PA que cobre o maior número de Pd’s.
    • Se a condição de 150 Mbps não for violada, o índice do PA com maior cobertura de Pd’s é armazenado e esses Pd’s são removidos.
    • O algoritmo reinicia a busca do próximo PA que cobre mais Pd’s dentre os restantes.
  • Critério de Parada:
    • O algoritmo para quando cobre pelo menos 475 dos 500 Pd’s atendendo as restrições de consumo de banda e limite de Pa’s.

Primeira Iteração

  • O algoritmo conta o número de Pd’s cobertos por cada uma das 81 possíveis localizações para o 1º PA e soma os Mbps demandados.

  • O máximo de 202 Pd’s são cobertos pelo PA nas coordenadas (200, 200).

  • O total de 146 Mbps de demanda desses Pd’s não viola a condição de menor que 150 Mbps.

  • As coordenadas deste 1º PA são armazenadas.

  • Os 202 Pd’s cobertos por este PA são removidos por já estarem cobertos.

Segunda Iteração

  • O algoritmo realiza a mesma busca e contagem da primeira iteração, porém desconsiderando os Pd’s cobertos pelo 1º PA.

  • O máximo de 199 Pd’s são cobertos pelo PA nas coordenadas (600, 600).

  • O total de 141 Mbps de demanda destes Pd’s não viola a condição de menor que 150 Mbps.

  • Da mesma forma são armazenadas as coordenadas desse 2º PA.

  • Os 199 Pd’s cobertos por este PA também são removidos por já estarem cobertos.

Decima Sétima Iteração

  • O algoritmo para.

  • O resultado da busca retorna uma solução no mínimo local de 17 PA´s.

  • A condição de que sejam cobertos 95% ou 475 do total de 500 Pd’s é atendida.

  • A restrição de número de Pa’s menor que 100 é atendida.

  • A restrição de que a soma da demanda dos Pd’s cobertos por um Pa não exceda 150 Mbps é atendida.

  • As informações dos índices, número de Pd’s atendidos e total da demanda em Mbps de cada Pa podem ser recuperadas.

Gráfico da Solução

Gráfico de Espaços Discretos

Gráfico de Convergência

Gráfico de Tempo

Gráfico da Solução

Método AHP

Objetivos Critérios e Optimizadores



Critério Máximo Mbps


Critério Cobertura


Critério Número de Pa’s


Critério Unidade de Decisão


Resultado do AHP


Otimizador em Produção